import sun.reflect.generics.tree.Tree;

public class BinarySearchTree {

    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(5);
        binarySearchTree.insert(7);
        binarySearchTree.insert(2);
        binarySearchTree.insert(9);
        binarySearchTree.insert(4);
        binarySearchTree.insert(1);
        TreeNode findNode = binarySearchTree.search(1);
        System.out.println(findNode);
    }

     class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {}

        public TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root;

    public boolean insert (int key) {
        TreeNode keyNode = new TreeNode(key);
        if (root == null) {
            root = keyNode;
        } else {
            TreeNode curNode = root;
            TreeNode prevNode = curNode;
            while (curNode != null) {
                //相同的就不添加了
                if (key == curNode.val) {
                    return false;
                }
                //小于往左走
                else if (key < curNode.val) {
                    prevNode = curNode;
                    curNode = curNode.left;
                }
                //大于往右走
                else {
                    prevNode = curNode;
                    curNode = curNode.right;
                }
            }
            if (key < prevNode.val) {
                prevNode.left = keyNode;
            } else {
                prevNode.right = keyNode;
            }
        }
        return true;

    }

    /**
     * 思路：
     * 首先找到key的位置用cur标记 同时也必须记录好cur的prev
     * 然后看cur所在位置的情况：左空 / 左不空 / 右空 / 右不空
     *
     * @param key
     */
    public void remove (int key) {
        if (root == null) {
            return;
        }
        TreeNode curNode = root;
        TreeNode prevNode = null;

        /**
         * 寻找key所在的结点curNode
         */
        while (curNode != null){
            if (curNode.val == key) {
                break;
            } else if (key < curNode.val) {
                prevNode = curNode;
                curNode = curNode.left;
            } else {
                prevNode = curNode;
                curNode = curNode.right;
            }
        }

        /**
         * 调用子函数移除
         */
        removeKey(curNode, prevNode);
    }

    /**
     * 从结点的左右子树是否存在开始分析
     * 不存在：
     *    若是root：很好办 直接左空接右 右空接左
     *    若不是root：看child是parent的左树还是右树 左空接右 右空接左
     * 存在：找左子树的最大值 / 右子树的最小值 和要remove的数替换
     *    若是root：
     *    若不是root
     * @param child
     * @param parent
     */
    private void removeKey(TreeNode child, TreeNode parent){
        if (child.left == null) {
            if (child == root) {
                root = root.right;
            } else {
                if (child == parent.left) {
                    parent.left = child.right;
                } else {
                    parent.right = child.right;
                }
            }
        } else if (child.right == null) {
            if (child == root) {
                root = root.left;
            } else {
                if (child == parent.left) {
                    parent.left = child.left;
                } else {
                    parent.right = child.left;
                }
            }
        }
        //子树皆非空：找到右数中最小的进行替换（右数中最小的一定没有左树，但是可能有右树，所以这里有分支）
        else {
            TreeNode target = child.right;
            TreeNode targetParent = child;
            while (target != null) {
                if (target.left == null) {
                    break;
                } else {
                    targetParent = target;
                    target = target.left;
                }
            }
            child.val = target.val;
            targetParent.left = target.right;
        }
    }

    public TreeNode search (int key) {
        return searchChild(key, root);
    }

    public TreeNode searchChild (int key, TreeNode root) {
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            if (root.left == null) {
                return null;
            } else {
                return searchChild(key, root.left);
            }
        } else if (key > root.val){
            if (root.right == null) {
                return null;
            } else {
                return searchChild(key, root.right);
            }
        }
        return root;
    }
}
